package leetCode;

import java.util.ArrayDeque;

public class Q19 {
    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode cur = head;
        ArrayDeque<ListNode> deque = new ArrayDeque<>();

        while (cur!=null){
            deque.add(cur);
            cur = cur.next;
        }

        for(int i=1;i<n;i++){
            deque.removeLast();
        }

        //要删除cur
        cur = deque.removeLast();
        if(n == 1){
            if(deque.size()>0){
                ListNode listNode = deque.removeLast();
                listNode.next = null;
            }else {
                return null;
            }
        }else {
            //不是倒数第一
            if(deque.size()>0){
                ListNode listNode = deque.removeLast();
                listNode.next = cur.next;
            }else {
                return cur.next;
            }

        }

        return head;
    }
}
